
//面试题 02.04. 分割链表
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null){
            return null;
        }
        ListNode newNode = new ListNode(-1);
        ListNode cur1 = newNode;
        ListNode cur2 = head;
        while(cur2!=null){
            if(cur2.val<x){
                ListNode newnode = new ListNode(cur2.val);
                cur1.next=newnode;
                cur1=cur1.next;
            }
            cur2=cur2.next;
        }
        cur2 = head;
        while(cur2!=null){
            if(cur2.val>=x){
                ListNode newnode = new ListNode(cur2.val);
                cur1.next=newnode;
                cur1=cur1.next;
            }
            cur2=cur2.next;
        }
        cur1.next=null;
        return newNode.next;
    }
}



//108. 将有序数组转换为二叉搜索树
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution1 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0){
            return null;
        }
        return func(0,nums.length-1,nums);
    }
    public TreeNode func(int left,int right,int[] nums){
        if(right<left){
            return null;
        }
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=func(left,mid-1,nums);
        root.right=func(mid+1,right,nums);
        return root;
    }
}